package done.easy_601_700;

import com.study.common.TreeNode;
import org.junit.Test;

import java.util.*;

import static com.study.util.LogUtil.info;

/**
 * 637. Average of Levels in Binary Tree 二叉树的层平均值
 * <p>
 * 给定一个非空二叉树, 返回一个由每层节点平均值组成的数组.
 * <p>
 * 示例 1:
 * 输入:                 平均值
 * <p>
 * 3         <--  3.0
 * / \
 * 9  20       <-- 14.5
 * /  \
 * 15   7     <-- 11.0
 * <p>
 * 输出: [3, 14.5, 11]
 * 解释:
 * 第0层的平均值是 3,  第1层是 14.5, 第2层是 11. 因此返回 [3, 14.5, 11].
 *
 * @author 大硕
 * 2019-04-10 7:16 AM
 **/
public class AverageOfLevelsInBinaryTree {

    private List<Double> averageOfLevels(TreeNode root) {
        // 190410 first
        // 190606 second 做了好几遍，看了答案做出来的，一上来没思路
        List<Double> res = new ArrayList<>();
        Stack<TreeNode> head = new Stack<>();
        head.push(root);
        while (!head.isEmpty()) {
            Stack<TreeNode> stack = new Stack<>();
            int size = head.size();
            double sum = 0;
            while (!head.isEmpty()) {
                TreeNode tmp = head.pop();
                sum += tmp.val;
                if (tmp.left != null)
                    stack.push(tmp.left);

                if (tmp.right != null)
                    stack.push(tmp.right);
            }
            res.add(sum / size);
            head = stack;
        }
        return res;
    }

    @Test
    public void test() {
        TreeNode root = new TreeNode(3,
                9, new TreeNode(20,
                15, 7));
        info(averageOfLevels(root));
        info(new Double[]{3.0, 14.5, 11.0});
    }
}








































/*
public List<Double> averageOfLevels(TreeNode root) {
    List<Double> ans = new ArrayList<Double>();

    Stack<TreeNode> head = new Stack<TreeNode>();
    head.push(root);

    while (!head.empty()) {
        double size = head.size();
        double sum = 0;

        Stack<TreeNode> next = new Stack<TreeNode>();

        while (!head.isEmpty()) {
            TreeNode node = head.pop();
            sum += node.val;

            if(node.left != null) {
                next.push(node.left);
            }

            if(node.right != null) {
                next.push(node.right);
            }
        }

        // 平均值
        ans.add(sum / size);
        head = next;
    }
    return ans;
}
*/
